package day_2022_9_to_12.Day2;

import java.util.Arrays;

/**
 * @author haomin
 * @date 2022/11/28 22:06
 **/
public class Day1_1_Num813 {
    class Solution {
        public double largestSumOfAverages(int[] nums, int k) {
            int n = nums.length;
            int[] sum = new int[n + 1];
            for(int i = 0; i < n; i ++){
                sum[i + 1] = sum[i] + nums[i];
            }
            double[][] f = new double[n + 1][k + 1];
            for(int i = 1; i <= n; i ++) Arrays.fill(f[i], -Integer.MIN_VALUE);
            f[0][0] = 0;
            for(int i = 1; i <= n; i ++){
                for(int j = 1; j <= Math.min(i, k); j ++){
                    for(int l = 1; l <= i; l ++){
                        double last = 1.0 * (sum[i] - sum[l - 1]) / (i - l + 1);
                        f[i][j] = Math.max(f[i][j], f[l - 1][j - 1] + last);
                    }

                }
            }
            return f[n][k];
        }
    }
}